home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / convex_test / convex.c < prev   
Encoding:
C/C++ Source or Header  |  1995-02-06  |  3.5 KB  |  111 lines
  1. /*
  2.  * C code from the article
  3.  * "Testing the Convexity of a Polygon"
  4.  * by Peter Schorn and Frederick Fisher,
  5.  *    (schorn@inf.ethz.ch, fred@kpc.com)
  6.  * in "Graphics Gems IV", Academic Press, 1994
  7.  */
  8.  
  9. /* Program to Classify a Polygon's Shape */
  10.  
  11. #include <stdio.h>
  12.  
  13. typedef enum { NotConvex, NotConvexDegenerate,
  14.            ConvexDegenerate, ConvexCCW, ConvexCW } PolygonClass;
  15.  
  16. typedef struct { double x, y; } Point2d;
  17.  
  18. int WhichSide(p, q, r)        /* Given a directed line pq, determine    */
  19. Point2d          p, q, r;        /* whether qr turns CW or CCW.        */
  20. {
  21.     double result;
  22.     result = (p.x - q.x) * (q.y - r.y) - (p.y - q.y) * (q.x - r.x);
  23.     if (result < 0) return -1;    /* q lies to the left  (qr turns CW).    */
  24.     if (result > 0) return  1;    /* q lies to the right (qr turns CCW).    */
  25.     return 0;            /* q lies on the line from p to r.    */
  26. }
  27.  
  28. int Compare(p, q)        /* Lexicographic comparison of p and q    */
  29. Point2d        p, q;
  30. {
  31.     if (p.x < q.x) return -1;    /* p is less than q.            */
  32.     if (p.x > q.x) return  1;    /* p is greater than q.            */
  33.     if (p.y < q.y) return -1;    /* p is less than q.            */
  34.     if (p.y > q.y) return  1;    /* p is greater than q.            */
  35.     return 0;            /* p is equal to q.            */
  36. }
  37.  
  38. int GetPoint(f, p)        /* Read p's x- and y-coordinate from f    */
  39. FILE    *f;            /* and return true, iff successful.    */
  40. Point2d *p;
  41. {
  42.     return !feof(f) && (2 == fscanf(f, "%lf%lf", &(p->x), &(p->y)));
  43. }
  44.  
  45. int GetDifferentPoint(f, previous, next)
  46. FILE    *f;            /* Read next point into 'next' until it */
  47. Point2d previous, *next;    /* is different from 'previous' and    */
  48. {                /* return true iff successful.        */
  49.     int eof;
  50.     while((eof = GetPoint(f, next)) && (Compare(previous, *next) == 0));
  51.     return eof;
  52. }
  53.  
  54. /* CheckTriple tests three consecutive points for change of direction
  55.  * and for orientation.
  56.  */
  57. #define CheckTriple                            \
  58.     if ( (thisDir = Compare(second, third)) == -curDir )        \
  59.         ++dirChanges;                        \
  60.     curDir = thisDir;                        \
  61.     if ( thisSign = WhichSide(first, second, third) ) {        \
  62.         if ( angleSign == -thisSign )                \
  63.         return NotConvex;                    \
  64.         angleSign = thisSign;                    \
  65.     }                                \
  66.     first = second; second = third;
  67.  
  68. /* Classify the polygon vertices on file 'f' according to: 'NotConvex'    */
  69. /* 'NotConvexDegenerate', 'ConvexDegenerate', 'ConvexCCW', 'ConvexCW'.    */
  70. PolygonClass ClassifyPolygon(f)
  71. FILE                *f;
  72. {
  73.     int         curDir, thisDir, thisSign, angleSign = 0, dirChanges = 0;
  74.     PolygonClass result;
  75.     Point2d     first, second, third, saveFirst, saveSecond;
  76.  
  77.     if ( !GetPoint(f, &first) || !GetDifferentPoint(f, first, &second) )
  78.     return ConvexDegenerate;
  79.     saveFirst = first;    saveSecond = second;
  80.     curDir = Compare(first, second);
  81.     while( GetDifferentPoint(f, second, &third) ) {
  82.     CheckTriple;
  83.     }
  84.     /* Must check that end of list continues back to start properly */
  85.     if ( Compare(second, saveFirst) ) {
  86.     third = saveFirst; CheckTriple;
  87.     }
  88.     third = saveSecond;     CheckTriple;
  89.  
  90.     if ( dirChanges > 2 ) return angleSign ? NotConvex : NotConvexDegenerate;
  91.     if ( angleSign  > 0 ) return ConvexCCW;
  92.     if ( angleSign  < 0 ) return ConvexCW;
  93.     return ConvexDegenerate;
  94. }
  95.  
  96. int main()
  97. {
  98.     switch ( ClassifyPolygon(stdin) ) {
  99.     case NotConvex:          fprintf( stderr,"Not Convex\n");
  100.                   exit(-1); break;
  101.     case NotConvexDegenerate: fprintf( stderr,"Not Convex Degenerate\n");
  102.                   exit(-1); break;
  103.     case ConvexDegenerate:      fprintf( stderr,"Convex Degenerate\n");
  104.                   exit( 0); break;
  105.     case ConvexCCW:          fprintf( stderr,"Convex Counter-Clockwise\n");
  106.                   exit( 0); break;
  107.     case ConvexCW:          fprintf( stderr,"Convex Clockwise\n");
  108.                   exit( 0); break;
  109.     }
  110. }
  111.